package lc20240622;

public class MinHeap {
    private int[] heap;

    //最小堆的大小
    private int size;

    public MinHeap(int capacity){
        this.size=0;
        this.heap=new int[capacity];
    }
    public void insert(int value){
        if (size>=heap.length){
            throw new IllegalStateException("heap is full");
        }
        heap[size]=value;
        siftUp(size++);
    }

    //返回最小值
    public int extractMin(){
        int min=heap[0];
        heap[0]=heap[size-1];
        size--;
        siftDown(0);
        return min;
    }

    //向下调整
    private void siftDown(int index) {
        while (2*index+1<size){
            int smallerChildIndex=2*index+1;
            if (smallerChildIndex+1<size&&heap[smallerChildIndex]>heap[smallerChildIndex+1]){
                smallerChildIndex++;
            }
            if (heap[index]<=heap[smallerChildIndex]){
                break;
            }
            swap(index,smallerChildIndex);
            index=smallerChildIndex;
        }

    }

    //向上调整
    private void siftUp(int index) {
        while (index>0&&heap[index]<heap[(index-1)/2]){
            swap(index,(index-1)/2);
            index=(index-1)/2;
        }
    }
    private void swap(int index, int smallerChildIndex) {
        int temp=heap[index];
        heap[index]=heap[smallerChildIndex];
        heap[smallerChildIndex]=temp;
    }
    public int size(){
        return size;
    }
    public boolean isEmpty(){
        return size==0;
    }
}
